package leetcode.pre100;

import utils.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：3
 * 输出：
 * [
 *   [1,null,3,2],
 *   [3,2,null,1],
 *   [3,1,null,null,2],
 *   [2,1,3],
 *   [1,null,2,null,3]
 * ]
 * 解释：
 * 以上的输出对应以下 5 种不同结构的二叉搜索树：
 * <p>
 * 1         3     3      2      1
 * \       /     /      / \      \
 * 3     2     1      1   3      2
 * /     /       \                 \
 * 2     1         2                 3
 * 提示：
 * <p>
 * 0 <= n <= 8
 *
 * @date 2020/4/7 16:35
 */


public class Code95_BSTNums_二叉搜索树个数1 {
    public static void main(String[] args) {
        List<TreeNode> list = new Code95_BSTNums_二叉搜索树个数1().generateTrees(3);
        System.out.println(list);
    }

    /**
     * 一个TreeNode代表一棵树
     *
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new LinkedList<>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);
    }

    /**
     * 我们只需要把 1 作为根节点，[ ] 空作为左子树，[ 2 ... n ] 的所有可能作为右子树。
     * <p>
     * 2 作为根节点，[ 1 ] 作为左子树，[ 3...n ] 的所有可能作为右子树。
     * <p>
     * 3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[ 4 ... n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
     * <p>
     * 4 作为根节点，[ 1 2 3 ] 的所有可能作为左子树，[ 5 ... n ] 的所有可能作为右子树，然后左子树和右子树两两组合。
     * <p>
     * ...
     * <p>
     * n 作为根节点，[ 1... n ] 的所有可能作为左子树，[ ] 作为右子树。
     * <p>
     * 至于，[ 2 ... n ] 的所有可能以及 [ 4 ... n ] 以及其他情况的所有可能，可以利用上边的方法，
     * <p>
     * 把每个数字作为根节点，然后把所有可能的左子树和右子树组合起来即可。
     * <p>
     * 如果只有一个数字，那么所有可能就是一种情况，把该数字作为一棵树。而如果是 [ ]，那就返回 null。
     * <p>
     *
     * @param start
     * @param end
     * @return
     */

    private List<TreeNode> getAns(int start, int end) {
        List<TreeNode> ans = new LinkedList<>();
        //此时没有数字，将 null 加入结果中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        //只有一个数字，当前数字作为一棵树加入结果中
        if (start == end) {
            TreeNode tree = new TreeNode(start);
            ans.add(tree);
            return ans;
        }
        //尝试每个数字i作为根节点
        for (int iRoot = start; iRoot <= end; iRoot++) {
            //得到所有可能的左子树
            List<TreeNode> leftTrees = getAns(start, iRoot - 1);
            //得到所有可能的右子树
            List<TreeNode> rightTrees = getAns(iRoot + 1, end);
            //左子树右子树两两组合
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(iRoot);
                    root.left = leftTree;
                    root.right = rightTree;
                    //加入到最终结果中
                    ans.add(root);
                }
            }
        }
        return ans;
    }

}
